A multi-core or multiprocessor operating system (OS) frequently needs to decide whether or not a thread (or any unit of OS scheduling) should migrate to a different core (or processing element in general) to maintain good balance and high utilization of the system. Thread migration introduces both benefits (e.g., more balanced system load) and overhead. As the number of cores grows, migration overhead increases as well, especially in systems with non-uniform memory access (NUMA) times (e.g., due to cores connecting to different memory controllers). When the overhead of migration eventually dominates its benefits, system performance will suffer significantly. Therefore, to effectively exploit the computing power of current multi-core and future tera-scale platforms, it is important that the OS efficiently control thread migrations and minimize their overheads.
The overhead of a thread migration includes two parts: the movement overhead and the cache miss overhead. The movement overhead is the overhead of moving the thread from the run queue of one core to that of another core. The cache miss overhead includes the overhead of resolving the extra cold misses that the thread incurs after the migration and the overhead of possibly accessing remote memory if the thread migrates to a different NUMA node.
Existing operating systems use the cache hot algorithm to predict migration overhead. When the OS is about to migrate a thread from core A to core B, this algorithm considers the local caches on A to be hot if the time that has elapsed since the thread's previous execution on A is less than some threshold. If this analysis indicates that the local caches on A are hot, the cache hot algorithm predicts the thread's migration overhead to be high. This algorithm, however, is highly inaccurate, and thus often leads to poor performance. For example, if a thread gets to run only briefly and blocks for an IO request, the thread does not have sufficient time to re-warm the cache during its short execution time. The cache hot algorithm, however, would still consider this thread cache to be hot, because the thread ran very recently, even though the cache is not actually hot (i.e., even though the cache does not contain much data for the thread).